package leetcode

import "fmt"

// Rotate rotate an array k
func Rotate(nums []int, k int) {
	l := len(nums)
	for i := 0; i < k; i++ {
		tmp := nums[l-1]
		copy(nums[1:], nums[0:])
		nums[0] = tmp
	}
}

// PrisonAfterNDays PrisonAfterNDays
func PrisonAfterNDays(cells []int, N int) []int {
	n := N % 14
	if n == 0 {
		n += 14
	}
	l := len(cells)
	preCells := make([]int, l)
	for i := 0; i < n; i++ {
		copy(preCells, cells)
		cells[0] = 0
		cells[7] = 0
		for j := 1; j < l-1; j++ {
			if preCells[j-1] == preCells[j+1] {
				cells[j] = 1
			} else {
				cells[j] = 0
			}
		}
		fmt.Println(cells)
	}
	return cells
}

func longestWidths(T []int) []int {
	var result = make([]int, len(T))
	for i := 0; i < len(T); i++ {
		cur := T[i]
		for j := i; j < len(T); j++ {
			if cur <= T[j] {
				result[i] = j - i + 1
			} else {
				break
			}
		}
		if i > 0 {
			for j := i - 1; j >= 0; j-- {
				if cur <= T[j] {
					result[i]++
				} else {
					break
				}
			}
		}
	}
	return result
}

// LargestRectangleArea1 largest rectangle Area
func LargestRectangleArea1(heights []int) int {
	widths := longestWidths(heights)
	//fmt.Println(widths)
	var maxArea int
	for i := 0; i < len(heights); i++ {
		area := heights[i] * (widths[i])
		if area > maxArea {
			maxArea = area
		}
	}
	return maxArea
}

func largestRectangleArea2(heights []int) int {
	var width int
	var maxArea int
	for i := 0; i < len(heights); i++ {
		cur := heights[i]
		for j := i; j < len(heights); j++ {
			if cur <= heights[j] {
				width = j - i + 1
			} else {
				break
			}
		}
		if i > 0 {
			for j := i - 1; j >= 0; j-- {
				if cur <= heights[j] {
					width++
				} else {
					break
				}
			}
		}
		area := heights[i] * (width)
		if area > maxArea {
			maxArea = area
		}
	}
	return maxArea
}

func largestRectangleArea(heights []int) int {
	heights = append(heights, 0)
	l := len(heights)
	s := newStack()
	var maxArea int
	for i := 0; i < l; i++ {
		for {
			if s.Len() != 0 {
				top := s.Peek()
				if heights[top] >= heights[i] {
					s.Pop()
					var area int
					if s.Len() == 0 {
						area = heights[top] * i
					} else {
						area = heights[top] * (i - s.Peek() - 1)
					}
					if area > maxArea {
						maxArea = area
					}
				} else {
					break
				}
			} else {
				break
			}
		}
		s.Push(i)
	}
	return maxArea
}
